#include <stdlib.h>
#include <stdbool.h>
#include "BST.h"

Node *createNode(int x) {
  Node *newNode = (Node*)malloc(sizeof(Node));
  newNode->key = x;
  newNode->left = newNode->right = NULL;
  return newNode;
}

Node *insertNode(Node **proot, int x) {
  while(true) {
    if(*proot == NULL) {
      return *proot = createNode(x);
    }
    if((*proot)->key == x) {
      return NULL;
    }
    if((*proot)->key > x) {
      proot = &(*proot)->left;
    } else {
      proot = &(*proot)->right;
    }
  }
}

Node *findNode(Node *root, int x) {
  while(true) {
    if(root == NULL) {
      return NULL;
    }
    if(root->key == x) {
      return root;
    }
    if(root->key > x) {
      root = root->left;
    } else {
      root = root->right;
    }
  }
}

// Deletes and returns as result the minimum node in the non-empty tree.
// Since the tree is non-empty, such minimum node must exist.
Node *deleteMin(Node **proot) {
  while(true) {
    if((*proot)->left == NULL) {
      // root is the minimum node, remove it from the tree and return it
      Node *minNode = *proot;
      *proot = (*proot)->right;
      return minNode;
    } else {
      // Keep moving down-left
      proot = &(*proot)->left;
    }
  }
}

Node *deleteNode(Node **proot, int x){
  while(true) {
    if(*proot == NULL) {
      // Cannot find key, deletion fails
      return NULL;
    }
    if((*proot)->key == x) {
      // Case 1: the node is a leaf
      // Note: this case is in fact a special case of the next one (case 2-a
      // or case 2-b) so this code could be merged with the next case.
      // We keep this case separate here for clarity.
      if((*proot)->left == NULL && (*proot)->right == NULL) {
        Node *deleted = *proot;
        *proot = NULL;
        return deleted;
      }
      // Case 2-a: the node has one left child
      if((*proot)->left != NULL && (*proot)->right == NULL) {
        Node *deleted = *proot;
        *proot = (*proot)->left;
        return deleted;
      }
      // Case 2-b: the node has one right child
      if((*proot)->left == NULL && (*proot)->right != NULL) {
        Node *deleted = *proot;
        *proot = (*proot)->right;
        return deleted;
      }
      // Case 3: the node has two children
      // We replace the root with the minimum node in the right subtree
      // (The maximum node in the left subtree would work too.)
      if((*proot)->left != NULL && (*proot)->right != NULL) {
        Node *deleted = *proot;
        // Find the minimum node in the right subtree:
        Node *minNode = deleteMin(&(*proot)->right);
        // Replace the root with the minNode:
        minNode->left = (*proot)->left;
        minNode->right = (*proot)->right;
        *proot = minNode;
        // Return the deleted node (the old root):
        return deleted;
      }
    }
    if((*proot)->key > x) {
      proot = &(*proot)->left;
    } else {
      proot = &(*proot)->right;
    }
  }
}

// This function cannot be changed to use a loop, unless you also add a
// stack data structure to keep track of which root->right nodes still need
// to be destroyed.
void destroyTree(Node *root) {
  if(root == NULL) {
    return;
  }
  destroyTree(root->left);
  destroyTree(root->right);
  free(root);
}
